package com.zjj.algorithm.learning.leetcode.tree.search;

/**
 * 96. 不同的二叉搜索树 中档题
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 * 输入：n = 3
 * 输出：5
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：1
 *
 * @author zjj_admin
 * @date 2022/11/28 10:41
 */
public class UniqueBinarySearchTrees {

    public static void main(String[] args) {

        int res = numTrees(5);
        System.out.println("res = " + res);

    }


    /**
     * n = 1 时，num = 1
     * n = 2 时，num = 2
     * n = 3 时，num = 5
     * <p>
     * 5 = 2 + 1 + 2 (2 为当 1位根节点，1 为当 2 为根节点，3 为 当 3 为根节点)
     * <p>
     * n = 4 时，num = 14（5 + 2 + 2 + 5）分别对应 1,2,3,4为根节点
     * <p>
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 38.3 MB
     * 击败
     * 52.79%
     *
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        int[] arr = new int[30];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        //当n <= 2 时直接返回即可
        if (n <= 2) {
            return arr[n];
        }
        //当 n >= 3 时
        for (int i = 3; i <= n; i++) {
            arr[i] = 0;
            for (int j = 1; j <= i; j++) {
                int m = j - 1;
                int k = i - j;
                if (m == 0) {
                    arr[i] += arr[k];
                }
                if (k == 0) {
                    arr[i] += arr[m];
                }
                if (m != 0 && k != 0) {
                    arr[i] += arr[m] * arr[k];
                }
            }
        }
        return arr[n];
    }
}
